package basic.study.leetcode;

import java.util.*;

/**
 * @ClassName Mid39
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/19 11:45
 * @Version 1.0
 */
public class Mid39 {
    static class Solution {
        List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            if (candidates == null || candidates.length == 0 || target < 0) {
                return res;
            }
            // 排序是为了提前终止搜索
            Arrays.sort(candidates);
            recall(0, candidates, target, 0, new ArrayList<>());
            return res;
        }

        public void recall(int start, int[] candidates, int target, int curSum, List<Integer> list) {
            if (curSum > target) {//剪枝
                return;
            }
            if (curSum == target) {//结果
                res.add(new ArrayList<>(list));
                return;
            }
            /**
             * 因为每次递归我们都是从 0 开始，所有数字都遍历一遍。所以会出现重复的组合。改进一下，只需加一个 start 变量即可。
             */
            for (int i = start; i < candidates.length; i++) {
                int ca = candidates[i];
                list.add(ca);
                recall(i, candidates, target, curSum+ca, list);
                list.remove(list.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.combinationSum(new int[]{2,3,6,7}, 7));
    }
}
